package xyz.scootaloo.oj.offer

import org.junit.Test
import xyz.scootaloo.oj.ds.TreeNode
import xyz.scootaloo.oj.ds.helper.CollectionBuilder
import java.util.*
import kotlin.collections.ArrayDeque
import kotlin.collections.ArrayList

/**
 * @author flutterdash@qq.com
 * @since 2021/4/11 9:26
 */
class P32III {

    /**
     * 3
     * 20, 9
     */
    fun levelOrder(root: TreeNode?): List<List<Int>> {
        val res = ArrayList<List<Int>>()
        if (root == null) return res
        var deque = LinkedList<TreeNode>()
        deque.add(root)

        var order = true
        while (deque.isNotEmpty()) {
            val level = LinkedList<TreeNode>()
            val levelValues = ArrayList<Int>()
            val iterator = deque.listIterator(if (order) 0 else deque.size)
            if (order) { // 从左到右
                while (iterator.hasNext()) {
                    val node = iterator.next()
                    levelValues.add(node.`val`)
                    if (node.left != null) {
                        level.addLast(node.left)
                    }
                    if (node.right != null) {
                        level.addLast(node.right)
                    }
                }
            } else { // 从右边到左
                while (iterator.hasPrevious()) {
                    val node = iterator.previous()
                    levelValues.add(node.`val`)
                    if (node.right != null) {
                        level.addFirst(node.right)
                    }
                    if (node.left != null) {
                        level.addFirst(node.left)
                    }
                }
            }
            res.add(levelValues)
            order = !order
            deque = level
        }

        return res
    }

    @Test
    fun test0() {
        val root = CollectionBuilder.initTree()
            .setRoot(3)
            .addLevel(9, 20)
            .addLevel(null, null, 15, 7)
            .addLevel(null, null, null, null, 11, 23)
            .build()
        println(levelOrder(root))
    }

}
